package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : leetcode0042 
* @author      : ganwei 
* @date        : 2020年5月14日 
* @Description : 42. 接雨水 
*/
public class leetcode0042 {
	/**
	 * -按列暴力求解
	 */
    public int trap(int[] height) {
    	int sum = 0;
    	for(int i = 1; i < height.length-1; i++) {
    		int max_left = 0;
    		int max_right = 0;
    		//找出左面最高
    		for(int j = i-1; j >= 0; j--) {
    			if(height[j] > max_left) {
    				max_left = height[j];
    			}
    		}
    		//找出右面最高
    		for(int j= i+1; j < height.length; j++) {
    			if(height[j] > max_right) {
    				max_right = height[j];
    			}
    		}
    		
    		int min = Math.min(max_left, max_right);
    		if(min > height[i]) {
    			sum += min-height[i];
    		}
    	}
    	
    	return sum;
    }

    /**
     * -动态规划解法
     */
    public int trap_1(int[] height) {
    	int sum = 0;
    	int[] max_left = new int[height.length];
    	int[] max_right = new int[height.length];
    	//动态规划求解左侧最高
    	for(int i = 1; i < height.length; i++) {
    		max_left[i] = Math.max(max_left[i-1], height[i-1]);
    	}
    	//动态规划求解右侧最高
    	for(int j = height.length-2; j >=0; j--) {
    		max_right[j] = Math.max(max_right[j+1], height[j+1]);
    	}
    	
    	//求和
    	for(int i = 1; i < height.length-1; i++) {
    		int min = Math.min(max_left[i], max_right[i]);
    		if(min > height[i]) {
    			sum += min-height[i];
    		}
    	}
    	
    	return sum;
    }
    
    public static void main(String[] args) {
    	
    }
}
